package com.lordjoe.sudoku;

import java.io.*;

/**
 * com.lordjoe.sudoku.SudokuBoard
 * This is the main object - implements the board and has a solve method
 * User: Steve
 * Date: 4/7/12
 */
public class SudokuBoard {
    public static final SudokuBoard[] EMPTY_ARRAY = {};

    public static final boolean SHOW_INTERMEDIATE_VALUES = true;

    private static int gBoxSize = 3;   // size of a box 3 for 9 * 9 Sudoku
    // simple cases may use 2
    private static int gBoardSize = gBoxSize * gBoxSize;

    public static void breakHere() {
    }


    public static int getBoxSize() {
        return gBoxSize;
    }

    /**
     * normal puzzle is 9 x 9 box size = 3 
     * 9 = 3 squared
     * @param pBoxSize
     */
    public static void setBoxSize(final int pBoxSize) {
        gBoxSize = pBoxSize;
        gBoardSize = gBoxSize * gBoxSize;  // also set board size
    }

    /**
     *  normal puzzle is 9 x 9 board size = 9
     * @return
     */
    public static int getBoardSize() {
        return gBoardSize;
    }

    public static final int NUMBER_CONSTRAINT_TYPES = 3; // row, column, block
    public static final int MAXMUM_PROPAGATION_STEPS = 10000;  // or we give up

    // all cells in the puzzle
    private SudokuCell[] m_Cells = new SudokuCell[getBoardSize() * getBoardSize()];
    // all constrainte
    private SudokuConstraint[] m_Constraints = new SudokuConstraint[getBoardSize() * NUMBER_CONSTRAINT_TYPES];
    // temporary variable
    private boolean m_ValueSetThisIteration; // if true at least one cell has set a value

    public SudokuBoard() {
        // make cells and constraints
        buildBoard();
    }

    /**
     * ****************************************************
     * This section is bookkeeping                        *
     * *****************************************************
     */
    /**
     * set the known cells as shown in the solution
     * @param sol !null solution
     */
    protected void setStart(SudokuSolution sol) {
        for (int col = 0; col < getBoardSize(); col++) {
            for (int row = 0; row < getBoardSize(); row++) {
                Integer val = sol.getValue(col, row);
                if (val != null)
                    getCell(col, row).setSpecifiedValue(val);
            }
        }
        resetMessaging();
     }

    /**
     * in the current iteration has a cell got a value - if so we will
     * not insert the hihgest probability guess
     * @return
     */
    public boolean isValueSetThisIteration() {
        return m_ValueSetThisIteration;
    }

    public void setValueSetThisIteration(final boolean pValueSetThisIteration) {
        m_ValueSetThisIteration = pValueSetThisIteration;
    }

    /**
     * create cells and constraints 
     * only done in initialization
     */
    protected void buildBoard() {
        buildCells();
        buildConstraints();
    }

    public boolean isCorrect() {
        for (int i = 0; i < m_Constraints.length; i++) {
            SudokuConstraint constraint = m_Constraints[i];
            if (!constraint.isSatisfied())
                return false; // one error
        }
        return true; // all OK
    }

    public SudokuConstraint getFirstUnsatisfiedConstraint() {
        for (int i = 0; i < m_Constraints.length; i++) {
            SudokuConstraint constraint = m_Constraints[i];
            if (!constraint.isSatisfied())
                return constraint; // one error
        }
        return null; // all OK
    }

    /**
     * the solution is complete
     *
     * @return
     */
    public boolean isComplete() {
        for (int i = 0; i < m_Cells.length; i++) {
            SudokuCell cell = m_Cells[i];
            if (!cell.hasValue())
                return false; // one error
        }
        return true; // all OK
    }



    /**
     * create cells 
     * only done in initialization
     */
    protected void buildCells() {
        int offset = 0;
        for (int col = 0; col < getBoardSize(); col++) {
            offset = col * getBoardSize();
            for (int row = 0; row < getBoardSize(); row++) {
                m_Cells[getIndex(col, row)] = new SudokuCell(col, row,this);
            }

        }
    }

    /**
     * prine the current state - that is any known cells
     * @param out  !null output stream usually System.out
     */
    public void showCells(PrintStream out) {
        out.println();
        for (int col = 0; col < getBoardSize(); col++) {
            out.print("|");
            for (int row = 0; row < getBoardSize(); row++) {
                SudokuCell cell = getCell(col, row);
                if (cell.hasValue())
                    out.print(cell.getValue());
                else
                    out.print(" ");
                out.print("|");
            }
            out.println();

        }
    }



    /**
     * create  constraints 
     * only done in initialization
     */
    protected void buildConstraints() {
        int index = 0;
        // build column constraints
        for (int col = 0; col < getBoardSize(); col++) {
            m_Constraints[index + col] = new SudokuConstraint(ConstraintType.Column, col, this);
        }
        // build row constraints
        index += getBoardSize();
        for (int row = 0; row < getBoardSize(); row++) {
            m_Constraints[index + row] = new SudokuConstraint(ConstraintType.Row, row, this);
        }
        // build box constraints
        index += getBoardSize();
        for (int box = 0; box < getBoardSize(); box++) {
            m_Constraints[index + box] = new SudokuConstraint(ConstraintType.Box, box, this);
        }

    }

    public SudokuConstraint getConstraint(ConstraintType type, int row) {
        return m_Constraints[getCostraintIndex(type, row)];
    }

    /**
     * look up a cell by row and column
     * @param row  
     * @param col
     * @return  !null cell for legal row and col
     */
    public SudokuCell getCell(int row, int col) {
        return m_Cells[getIndex(row, col)];
    }

    /**
     * index into linear array for row and column
     * @param col
     * @param row
     * @return index into linear array
     */
    protected int getIndex(int col, int row) {
        return col * getBoardSize() + row;
    }
    /**
     * look up a cell from box and index 0 used by box constraints
     * @param box
     * @param index
     * @return
     */
    public SudokuCell getCellFromBox(final int box, final int index) {
        return m_Cells[getBoxIndex(box, index)];
    }

    /**
     * given a box and the index into it get the index in the cell array
     *
     * @param box
     * @param index
     * @return
     */
    public int getBoxIndex(final int box, final int index) {
        int boxSize = getBoxSize();
        int startRow = boxSize * (box / boxSize);
        int startCol = boxSize * (box % boxSize);
        startRow += index / boxSize;
        startCol += index % boxSize;
        return getIndex(startRow, startCol);
    }

    protected int getCostraintIndex(ConstraintType type, int cellIndex) {
        return type.getIndex() * NUMBER_CONSTRAINT_TYPES + cellIndex;
    }

    /*******************************************************
     *  This section is the algorithm                        *
     *******************************************************/
    /**
     * propagate belief until solved
     */
    public boolean solve() {
        int steps = 0;
        initializeSolution();
        while (!isComplete()) {
            doSolutionStep(steps++);
            if (steps  > MAXMUM_PROPAGATION_STEPS)
                return false; // give up
        }
        if (isCorrect())
            return true; // solved
        throw new IllegalStateException("Incorrect solution");
    }

    /**
     * start probabilities with initial values
     */
    protected void initializeSolution() {
        for (SudokuCell cell : m_Cells) {
            cell.initializePhi();
        }
    }

    public static final int NUMBER_UNCHANGED_STEPS_BEFORE_GUESS = 10;
    /**
     * call until puzzle solved or ,ax retries achieved
     */
    protected void doSolutionStep(int step) {
        int stepsWithoutValueSet = 0;
        setValueSetThisIteration(false);
        resetMessaging(); // clear state for cells and constraints
        cellsMessageConstraints();  // cells message constraints
        constraintsMessageCells();  // get messages back
        resetCellStates();          // alter phi
        if (!isValueSetThisIteration()) {   // sometimes cells will have a value set if not try to force a state change
            SudokuCell cell = getBestCellToSet();
            if (cell != null)
                if(cell.getMaxProbability() > 0.99)  {
                    cell.maybeSetValue();
                 }
                else if(stepsWithoutValueSet++ >  NUMBER_UNCHANGED_STEPS_BEFORE_GUESS  )  {
                    cell.maybeSetValue();
                    stepsWithoutValueSet = 0;
                }
             //   else
              //      cell.unBalance();
        }
        if (!isCorrect()) { // validate
            System.out.println(getFirstUnsatisfiedConstraint());
            showCells(System.out);
            throw new IllegalStateException("Incorrect solution");
        }
    }

    /**
     * reset for a new round of messaging
     */
    public void resetMessaging() {
        resetCellMessaging();
        resetConstraintMessaging();
    }

    private void resetConstraintMessaging() {
        for (SudokuConstraint constraint : m_Constraints) {
            constraint.resetMessaging();
        }
    }

    protected void resetCellMessaging() {
        for (SudokuCell cell : m_Cells) {
            cell.resetMessaging();
        }
    }

    /**
     * send messages from cells to constraints
     */
    protected void cellsMessageConstraints() {
        for (SudokuCell cell : m_Cells) {
            cell.messageConstraints();
        }
    }


    /**
      * send messages from   constraints to cells
      */
    protected void constraintsMessageCells() {
        for (SudokuConstraint constraint : m_Constraints) {
            constraint.messageCells();
        }

    }


    /**
     * after getting constraint messages update the cells probabilities (phi)
     */
    protected void resetCellStates() {
        for (SudokuCell cell : m_Cells) {
            cell.resetStateAfterMessaging();
        }
    }

    /**
     * if no cells have been set consider guessing the value of the cell with the
     * highest probability for a value
     * @return  possibly null cell with best probability for a single value
     */
    protected SudokuCell getBestCellToSet() {
        double bestProbability = Double.MIN_VALUE;
        SudokuCell ret = null;
        for (SudokuCell cell : m_Cells) {
            // ignore already set cells
            if (cell.hasValue())
                continue;
            double maxProbability = cell.getMaxProbability();
            if (maxProbability > bestProbability) {
                bestProbability = maxProbability;
                ret = cell;
            }
        }
        return ret;
    }


    /**
     * ****************************************************
     * This section is the test code                        *
     * *****************************************************
     */

    private static SudokuBoard buildGame() {
        setBoxSize(3);
        SudokuBoard game = new SudokuBoard();
        game.setStart(SudokuSolution.SOLN1);
        if (!game.isCorrect())
            throw new IllegalStateException("incorrect board");
        return game;
    }

    private static SudokuBoard buildGame(String start) {
        setBoxSize(3);
        SudokuBoard game = new SudokuBoard();
        game.setStart(new SudokuSolution(start));
        if (!game.isCorrect())
            throw new IllegalStateException("incorrect board");
        return game;
    }


    private static SudokuBoard buildBadGame() {
        setBoxSize(3);
        SudokuBoard game = new SudokuBoard();
        game.setStart(SudokuSolution.SOLN1_BAD);
        if ( game.isCorrect())
            throw new IllegalStateException("shouold be incorrect board");
        return game;
    }


    private static SudokuBoard buildGame2X2X() {
        setBoxSize(2);
        SudokuBoard game = new SudokuBoard();
        game.setStart(new SudokuSolution(SudokuSolution.VALUES_2_BY_2X));
        if (!game.isCorrect())
            throw new IllegalStateException("incorrect board");
        return game;
    }


    private static SudokuBoard buildGame2X2() {
        setBoxSize(2);
        SudokuBoard game = new SudokuBoard();
        game.setStart(new SudokuSolution(SudokuSolution.VALUES_2_BY_2));
        if (!game.isCorrect())
            throw new IllegalStateException("incorrect board");
        return game;
    }


    private static SudokuBoard buildGame2X2BAD() {
        setBoxSize(2);
        SudokuBoard game = new SudokuBoard();
        game.setStart(new SudokuSolution(SudokuSolution.VALUES_2_BY_2_BAD));
        if (game.isCorrect())
            throw new IllegalStateException("should be incorrect board");
        return game;
    }

    public static final int MAX_SOLUTION_ITERATIONS = 10000;

    /**
     * seting is 81 digits 0.. 9
     * @param gameData
     */
    public static void solveSuduku(String gameData)
    {
        SudokuBoard game = buildGame(gameData);
        solveSudoku(game);

    }

    /**
     * board to solue
     * @param pGame  !null board
     */
    public static void solveSudoku(final SudokuBoard pGame) {
        pGame.initializeSolution();
        if (pGame.isComplete()) {
            System.out.println("Solved!!");
            pGame.showCells(System.out);

        }

        System.out.println("Start!!");
        pGame.showCells(System.out);
         int steps = 0;
        while (!pGame.isComplete()) {
                pGame.doSolutionStep(steps++);
            if(pGame.isValueSetThisIteration() &&   SHOW_INTERMEDIATE_VALUES)    {
                System.out.println("Step = " + steps);
                pGame.showCells(System.out);
            }
            if (steps > MAX_SOLUTION_ITERATIONS)  {
                break;
            }
        }
        if(pGame.isComplete())
            System.out.println("Done Correctly after " + steps +  " steps");
        else
            System.out.println("Gave up after " + steps + " tries");
    }

    public static final String SAMPLE_PUZZLE =
            "300704280000060000050000730540003090009080600060900025036000070000070000072806004";

    public static void main(String[] args) {
        // buildBadGame();
        //   buildGame();
        if(args.length == 0)
            solveSuduku(SAMPLE_PUZZLE);
        else
            solveSuduku(args[0]);
     }

}
